1. Technical Field
The present application relates generally to an improved data processing system and method. More specifically, the present application is directed to a system and method for garbage collection in heterogeneous multiprocessor systems.
2. Description of Related Art
When computer programs execute, they allocate memory for data buffers. When the computer program continues to allocate such memory, it may eventually exceed the physical memory capacity. In such a situation, the operating system must place portions of the program in virtual memory, i.e. on disk, in order to continue executing, which slows down execution of the computer program. Manually deallocating memory after a routine no longer needs that portion of memory is a tedious task which programmers often forget to do, or do not do properly.
As an alternative to manual deallocation of memory, garbage collection was developed. Garbage collection is the use of a software routine that searches memory for areas of inactive data and instructions in order to reclaim that space for the general memory pool, i.e. the heap. A garbage collector basically works by determining what data objects in a program will not be accessed in the future execution of the program, and reclaiming storage used by those objects.
Garbage collection automates the freeing up of memory so that the programmer no longer has to worry about releasing objects that are no longer needed. As a result, this source of considerable program design effort may be avoided. Moreover, garbage collection aids in making programming languages safer due to the reduction in several classes of runtime errors, e.g., dangling pointer errors where a reference to a deallocated object is used.
Many computer programming languages, referred to as garbage-collected languages, now require garbage collection either as part of the language specification (e.g., Java, C#, and most scripting languages) or effectively for practical implementation (e.g., formal languages like lambda calculus). Other computer programming languages are designed for use with manual memory management, but have garbage collected implementations (e.g., C, C++). Other computer programming languages, such as Modula-3, allow both garbage collection and manual memory management to co-exist in the same application by using separate heaps for collected and manually managed objects.
Tracing garbage collectors are the most common type of garbage collector. Tracing garbage collectors focus on determining which objects are reachable, or potentially reachable, and then discarding all remaining objects. A reachable object may be defined as an object for which there exists some name in the program environment that leads to it, either directly or through references from other reachable objects. More precisely, objects can be reachable in only two ways. First, a distinguished set of objects are assumed to be reachable, these are known as the roots. Typically, these include all the objects referenced from anywhere in the call stack, i.e. all local variables and parameters in the functions currently being invoked, and any global variables. Second, anything referenced from a reachable object is itself reachable. This is referred to as transitivity.
Tracing garbage collectors use an algorithm in which they perform garbage collection cycles. A cycle is started when the collector decides, or is notified, that it needs to reclaim storage, which in particular happens when the system is low on memory. All tracing garbage collectors implement some variant of the tri-color marking abstraction, but simple collectors, such as the mark-and-sweep collector, often do not make this abstraction explicit. Tri-color marking works as follows.
First, initial white, grey and black sets are created that will be used to maintain progress during the cycle. Initially, the white set, or condemned set, is the set of objects that are candidates for having their memory recycled. The black set is the set of objects that can be easily proven to have no references to objects in the white set. In many implementations the black set starts off empty. The grey set is all the remaining objects that may or may not have references to objects in the white set. These sets partition memory such that every object in the system, including the root set, is in precisely one set.
Thereafter, an object in the grey set is selected. This object is blackened, i.e. moved to the black set, by “greying” all the white objects it references directly, i.e. blackening all the white objects that the object references and objects that they reference. This step is repeated until the grey set is empty. When there are no more objects in the grey set, then all the objects remaining in the white set are provably not reachable and the storage occupied by them can be reclaimed.
With the tri-color marking algorithm, no black object points directly to a white object. This ensures that the white objects can be safely destroyed once the grey set is empty.
Once the unreachable set, i.e. the resulting white set when the grey set is empty, has been determined, the garbage collector may simply release the unreachable objects and leave everything else as it is. Alternatively, the garbage collector may copy some or all of the reachable objects into a new area of memory, updating all references to those objects as needed. These are called “non-moving” and “moving” garbage collectors, respectively.
Tracing collectors may also be categorized by considering how the three sets of objects (white, grey, and black) are maintained during a collection cycle. The most straightforward approach is the semi-space collector, which is a moving garbage collection scheme in which memory is partitioned into a “from space” and “to space”. Initially, objects are allocated into “to space”, until it becomes full and a garbage collection cycle is triggered. At the start of the garbage collection, the “to space” becomes the “from space”, and vice versa. The objects reachable from the root set are copied from the “from space” to the “to space”. These objects are scanned in turn, and all objects that they point to are copied to “to space” until all reachable objects have been copied to “to space”. Once the program continues execution, new objects are once again allocated from the “to space” until it is once again full and the process is repeated. This approach has the advantage of conceptual simplicity, since the three object color sets are implicitly constructed during the copying process, but the disadvantage that a very large contiguous region of free memory may possibly be needed on every collection cycle.
In general, a “mark and sweep” garbage collector maintains one or two bits with each object to record whether it is white or black. The grey set is either maintained as a separate list or is identified using another bit. As the reference tree is traversed during a collection cycle, these bits are manipulated by the collector to reflect the current state, i.e. white, black, or grey. The mark and sweep strategy has the advantage that, once the unreachable set is determined, i.e., the resulting white set after the grey set is empty, either a moving or non-moving collection strategy can be pursued. This choice of strategy can even be made at runtime, as available memory permits.
In some implementations of garbage collectors, the mark and sweep garbage collector uses an explicit stack to store objects which are known to be reachable, but whose contents have not yet been examined (i.e. the “grey” objects). Each entry in the stack contains a base address and a mark descriptor, indicating the location of possible pointers relative to that starting address. Mark descriptors typically take the form of either a simple length specification, or a bit vector describing pointer locations.
In addition to the above, garbage collectors may also be of various types with regard to how they interrupt other operations of the system in which they operate. For example, “stop-the-world” garbage collectors completely halt execution of the program to run a collection cycle, thus guaranteeing that new objects are not allocated and objects do not suddenly become unreachable while the collector is running. This has the obvious disadvantage that the program can perform no useful work while a collection cycle is running.
“Incremental” garbage collectors are designed to reduce this disruption by interleaving their work with activity from the main program. Careful design is necessary to ensure that the main program does not interfere with the garbage collector and vice versa. For example, when the program needs to allocate a new object, the runtime system may either need to suspend it until the collection cycle is complete or somehow notify the garbage collector that there exists a new, reachable object.
Finally, a concurrent garbage collector can run concurrently in real time with the main program on a symmetric multiprocessing machine. Complex locking regimes may be necessary in order to guarantee correctness. Moreover, cache issues also make this less helpful than one might imagine. Nonetheless, concurrent GC may be desirable for SMP applications with high performance requirements.
The garbage collection mechanisms described above have been developed for data processing environments in which there is a uniformity of the processors, e.g., single processor or symmetric multiprocessing (SMP) systems. A number of issues may arise when attempting to apply such garbage collection mechanisms to non-uniform data processing systems, i.e. heterogeneous systems such as non-SMP co-processor systems, software managed memory systems, Non-Uniform Memory Access (NUMA) systems, and the like. Address format issues, address translation issues, when garbage collection may be performed so as to ensure that pointers to memory locations do not change, non-uniform memory latency, and the like, are but a few of the problems introduced by heterogeneous systems.